{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# String Compression\n",
    "\n",
    "## Problem\n",
    "\n",
    "Given a string in the form 'AAAABBBBCCCCCDDEEEE' compress it to become 'A4B4C5D2E4'. For this problem, you can falsely \"compress\" strings of single or double letters. For instance, it is okay for 'AAB' to return 'A2B1' even though this technically takes more space. \n",
    "\n",
    "The function should also be case sensitive, so that a string 'AAAaaa' returns 'A3a3'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution\n",
    "Since Python strings are immutable, we'll need to work off of a list of characters, and at the end convert that list back into a string with a **join** statement.\n",
    "\n",
    "The solution below should yield us with a Time and Space complexity of O(n). Let's take a look with careful attention to the explanatory comments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compress(s):\n",
    "    \"\"\"\n",
    "    This solution compresses without checking. Known as the RunLength Compression algorithm.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Begin Run as empty string\n",
    "    r = \"\"\n",
    "    l = len(s)\n",
    "    \n",
    "    # Check for length 0\n",
    "    if l == 0:\n",
    "        return \"\"\n",
    "    \n",
    "    # Check for length 1\n",
    "    if l == 1:\n",
    "        return s + \"1\"\n",
    "    \n",
    "    #Intialize Values\n",
    "    last = s[0]\n",
    "    cnt = 1\n",
    "    i = 1\n",
    "    \n",
    "    while i < l:\n",
    "        \n",
    "        # Check to see if it is the same letter\n",
    "        if s[i] == s[i - 1]: \n",
    "            # Add a count if same as previous\n",
    "            cnt += 1\n",
    "        else:\n",
    "            # Otherwise store the previous data\n",
    "            r = r + s[i - 1] + str(cnt)\n",
    "            cnt = 1\n",
    "            \n",
    "        # Add to index count to terminate while loop\n",
    "        i += 1\n",
    "    \n",
    "    # Put everything back into run\n",
    "    r = r + s[i - 1] + str(cnt)\n",
    "    \n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A5B4C4'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compress('AAAAABBBBCCCC')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test Your Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestCompress(object):\n",
    "\n",
    "    def test(self, sol):\n",
    "        assert_equal(sol(''), '')\n",
    "        assert_equal(sol('AABBCC'), 'A2B2C2')\n",
    "        assert_equal(sol('AAABCCDDDDD'), 'A3B1C2D5')\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "\n",
    "# Run Tests\n",
    "t = TestCompress()\n",
    "t.test(compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
